package immutablecollections;

import immutablecollections.exceptions.*;
import immutablecollections.functions.*;
import immutablecollections.misc.*;
import java.util.*;

/**
 * An ordered list of objects with addition, removal and access methods having performance **`O`**`(log n)`
 * where `n` is the number of elements in the shelf.
 * 
 * ## Introduction
 * 
 * <img src="doc-files/classes-focus-on-shelf.png" alt="classes-focus-on-shelf" style="width: 40em"/>
 * 
 * You could also think of this as an immutable version of `org.apache.commons.collections.list.TreeList`.
 * 
 * This is the nearest equivalent to java.util.List in the sense that add/find/remove/replace is relatively fast.
 * 
 * 
 * The idea of the name *Shelf* is that, if you have a collection of books on a bookshelf, then
 * the books are arranged in a sequence and it is reasonably quick
 * to add/find/replace/remove a book at an arbitrary position.
 * 
 * <img src="doc-files/shelf.png" alt="shelf" style="width: 20%"/>
 * 
 * 
 * 
 * # Standard ImCollection methods implemented by this class:
 * 
 * - {@link #onArray(Object...)}
 * - {@link #onAll(Collection)}
 * - {@link #on(Object)}
 * - {@link #empty()}
 * - {@link #joinArray(Collection...)}
 * - {@link #joinIterator(Iterator)}
 * - {@link #join(Collection)}
 * - {@link #addingAll(Collection)}
 * - {@link #upCast()}
 * - {@link #contains(Object)}
 * - {@link #size()}
 * - {@link #iterator()}
 * - {@link #getZipper()}
 * - {@link #toString()}
 * - {@link #map(Function1)}
 * 
 * See the <a href="{@docRoot}/immutablecollections/package-summary.html">package summary</a>
 * for more details of the standard methods.
 * 
 * ## Query
 * - {@link #get1(int)}
 * - {@link #indexOf1(Object)}
 * 
 * ## Mutation
 * 
 * - {@link #adding(Object)}
 * - {@link #adding(int, Object)}
 * - {@link #set1(int, Object)}
 * - {@link #remove1(int)}
 * 
 * ### Implementation Notes
 * 
 * A shelf keeps its elements in a balanced binary tree.
 * 
 * This shelf:
 * 
 *     [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
 * 
 * has a tree that looks something like this (the exact layout of the tree a will vary depending on 
 * the order in which the elements were added):
 * 
 *          4      
 *      .......    
 *      2     8    
 *     ...  .....  
 *     1 3  6   9  
 *         ... ... 
 *         5 7 - 10
 * 
 * If we add `0` to the front:
 * 
 *     [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
 *     
 * the new tree looks like this:
 * 
 *           4       
 *       ........    
 *       2      8    
 *      ....  .....  
 *      1  3  6   9  
 *     ...   ... ... 
 *     0 -   5 7 - 10
 * 
 * Only `4` new nodes need to be created - the other nodes can be shared with the previous tree.
 * 
 * If we add `11` to the end:
 * 
 *     [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
 *     
 * The new tree now looks like this:
 * 
 *           4       
 *       ........    
 *       2      8    
 *      ....  .....  
 *      1  3  6   10 
 *     ...   ... ... 
 *     0 -   5 7 9 11
 * 
 * Again, `4` new nodes are created.
 * 
 * See the <a href="{@docRoot}/immutablecollections/package-summary.html">package summary</a>
 * for more details.
 */
public class ImShelf<T> extends ImCollection<T>
{

    static class ImShelfIterator<T> implements Iterator<T>
    {
        ImTreeIterator<T> treeIterator;

        public ImShelfIterator(ImTreeIterator<T> treeIterator)
        {
            this.treeIterator = treeIterator;
        }

        public boolean hasNext()
        {
            return treeIterator.hasNext();
        }

        public T next()
        {
            return treeIterator.next();
        }

        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }

    /**
     * The singleton empty object
     */
    private static ImShelf<?> empty = new ImShelf<Object>();

    /**
     * The tree that holds the elements
     */
    final private ImTree<T> tree;

    /**
     * The constructor for the empty shelf
     */
    ImShelf()
    {
        this(ImTree.<T> Nil());
    }

    protected ImShelf(ImTree<T> tree)
    {
        this.tree = tree;
    }

    /**
     * The (singleton) empty shelf.
     * 
     */
    @SuppressWarnings("unchecked")
    public static <T> ImShelf<T> empty()
    {
        return onArray();
    }

    /**
     * The shelf whose elements are obtained from `array`.
     * 
     * ImCollections can't contain `null` so none of the elements in `array` can be `null`
     * 
     * ### Examples:
     * 
     *     on(1, 2, 3)                      => [1, 2, 3]
     *     on(new Integer[] { 1, 2, 3 })    => [1, 2, 3]
     *     on()                             => []
     *     on(null, 2, 3)                   => throws java.lang.NullPointerException: ImCollections can't contain nulls
     * 
     * @throws NullPointerException if any of the elements in `array` is `null`
     * @see #onAll(Collection)
     * @see #onIterator(Iterator)
     * @see #on
     */
    public static <A> ImShelf<A> onArray(A... array)
    {
        return onIterator(ArrayIterator.on(array));
    }

    /**
     * The shelf whose elements are obtained from `elementsCollection`.
     * 
     * ImCollections can't contain `null` so none of the elements in `elementsCollection` can be `null`
     * 
     * ### Examples:
     * 
     *     on(Arrays.asList(1, 2, 3))    => [1, 2, 3]
     *     on(Arrays.asList())           => []
     *     on(Arrays.asList(1, null, 3)) => throws java.lang.NullPointerException: ImCollections can't contain nulls
     * 
     * @throws NullPointerException if any of the elements in `elementsCollection` is `null`
     * @see #onIterator(Iterator)
     * @see #onArray(Object...)
     * @see #on
     */
    @SuppressWarnings("unchecked")
    public static <A> ImShelf<A> onAll(Collection<? extends A> elementsCollection)
    {
        return elementsCollection instanceof ImShelf
                ? (ImShelf<A>) elementsCollection
                : onIterator(elementsCollection.iterator());
    }

    /**
     * The shelf whose elements are obtained by iterating over `iterator`.
     * 
     * ImCollections can't contain `null` so none of the elements in `iterator` can be `null`
     * 
     * ### Examples:
     * 
     *     on(Arrays.asList(1, 2, 3).iterator())    => [1, 2, 3]
     *     on(Arrays.asList().iterator())           => []
     *     on(Arrays.asList(1, null, 3).iterator()) => throws java.lang.NullPointerException: ImCollections can't contain nulls
     * 
     * @throws NullPointerException if any of the elements in `iterator` is `null`
     * @see #onAll(Collection)
     * @see #onArray(Object...)
     * @see #on
     */
    @SuppressWarnings("unchecked")
    public static <A> ImShelf<A> onIterator(Iterator<? extends A> iterator)
    {
        ImShelf<A> result = (ImShelf<A>) empty;

        while (iterator.hasNext())
        {
            result = result.adding(iterator.next());
        }

        return result;
    }

    /**
     * The shelf whose only element is `element`.
     * 
     * This is convenient when we want to create a list whose only element is an array.
     * 
     * ImCollections can't contain `null` so `element` can't be `null`.
     * 
     * ### Examples
     * 
     *     on(1)   => [1]
     *     
     *     Integer[] ints = new Integer[] { 1, 2, 3 };
     *     assertEquals(1, on(ints).size());
     *     assertEquals(true, on(ints).at(1).getClass().isArray());
     *     
     * @throws NullPointerException if element is `null`
     * @see #onArray(Object...)
     * @see #onIterator(Iterator)
     * @see #onArray(Object[])
     */
    public static <A> ImShelf<A> on(A element)
    {
        return ImShelf.<A> empty().adding(element);
    }

    /**
     * Allows `ImShelf<U>` to be cast to `ImShelf<T>` (where U is a subtype of T) without generating a compiler warning.
     * 
     * For a detailed description see {@link ImList#upCast()}
     */
    @SuppressWarnings("unchecked")
    public <U> ImShelf<U> upCast()
    {
        return (ImShelf<U>) this;
    }

    /**
     * Add `elementToAdd` at index `indexStartingAtOne`.
     * 
     * All elements with `index >= indexStartingAtOne` are shuffled up.
     *
     * ImCollections can't contain `null` so `elementToAdd` must not be `null`
     * 
     * ### Examples:
     * 
     *     on(1, 2, 3, 5).adding(2, 8)  =>  [1, 8, 2, 3, 5]
     *     on(1, 2, 3).adding(4, 8)     =>  [1, 2, 3, 8]
     *     on(1, 2, 3).adding(13, 8)    =>  java.lang.IndexOutOfBoundsException: index should be in the range [1, 4]  but was 13
     *     
     * @throws IndexOutOfBoundsException
     */
    public ImShelf<T> adding(int indexStartingAtOne, T elementToAdd)
    {
        ImIndexOutOfBoundsException.check(indexStartingAtOne, 1, size() + 1, "index");
        NullCheck.check(elementToAdd);

        return new ImShelf<T>(getTree().insert(indexStartingAtOne, elementToAdd));
    }

    /**
     * Add `elementToAdd` at the end.
     * 
     * ImCollections can't contain `null` so `elementToAdd` must not be `null`
     * 
     * ### Examples:
     * 
     *     on(1, 2).adding(3)        =>  [1, 2, 3]
     *     on().adding(1)            =>  [1]
     *     on(1, 2, 3).adding(null)  =>  throws java.lang.NullPointerException: ImCollections can't contain nulls
     * 
     * @throws NullPointerException
     */
    public ImShelf<T> adding(T elementToAdd)
    {
        return adding(size() + 1, elementToAdd);
    }

    /**
     * A string representation of this shelf.
     * 
     * This representation is essentially the same as {@link ImList#toString()}
     */
    @Override
    public String toString()
    {
        return "[" + TextUtils.join(iterator(), ", ") + "]";
    }

    /**
     * The number of elements in `this`.
     */
    public int size()
    {
        return getTree().size();
    }

    public ImShelfIterator<T> iterator()
    {
        return new ImShelfIterator<T>(new ImTreeIterator<T>(getTree()));
    }

    /**
     * Set the element at index `indexStartingAtOne` to `elementToSet`.
     * 
     * ### Examples:
     * 
     *     on(1, 2, 3).set(1, 5)  =>  [5, 2, 3]
     *     on(1, 2, 3).set(3, 8)  =>  [1, 2, 8]
     *     on(1, 2).set(-1, 4)    =>  java.lang.IndexOutOfBoundsException: index should be in the range [1, 3]  but was -1
     *     
     * @throws IndexOutOfBoundsException
     * @throws NullPointerException
     */
    public ImShelf<T> set1(int indexStartingAtOne, T elementToSet)
    {
        ImIndexOutOfBoundsException.check(indexStartingAtOne, 1, size() + 1, "indexStartingAtOne");
        NullCheck.check(elementToSet);

        ImTreeZipper<T> path = ImTreeZipper.onRoot(getTree()).goToIndex(indexStartingAtOne);

        return new ImShelf<T>(path.replaceElement(elementToSet).close());
    }

    /**
     * Set the element at index `indexStartingAtZero` to `elementToSet`.
     * 
     * ### Examples:
     * 
     *     on(1, 2, 3).set(0, 5)  =>  [5, 2, 3]
     *     on(1, 2, 3).set(2, 8)  =>  [1, 2, 8]
     *     on(1, 2).set(-1, 4)    =>  java.lang.IndexOutOfBoundsException: index should be in the range [0, 2]  but was -1
     *     
     * @throws IndexOutOfBoundsException
     * @throws NullPointerException
     * @see #set1(int, Object)
     */
    public ImShelf<T> set(int indexStartingAtZero, T elementToSet)
    {
        ImIndexOutOfBoundsException.check0(indexStartingAtZero, size(), "indexStartingAtZero");
        return set1(indexStartingAtZero + 1, elementToSet);
    }

    /**
     * The element at index `indexStartingAtOne`.
     * 
     * ### Examples:
     * 
     *     on(1, 2, 3).get(1)  =>  1
     *     on(1, 2, 3).get(3)  =>  3
     *     on(1, 2).get(3)     =>  java.lang.IndexOutOfBoundsException: the size of the collection is 2 but indexStartingAtOne was 3
     *     on().get(1)         =>  java.lang.IndexOutOfBoundsException: The collection is empty but indexStartingAtOne was 1
     *     
     * @throws IndexOutOfBoundsException
     * @see #set(int, Object)
     */
    public T get1(int indexStartingAtOne)
    {
        return getTree().getNodeAtIndex(indexStartingAtOne).getElement();
    }

    /**
     * The element at index `indexStartingAtZero`.
     * 
     * ### Examples:
     * 
     *     onArray(1, 2, 3).get(0)  =>  1     
     *     onArray(1, 2, 3).get(2)  =>  3
     *     onArray().get(0)         =>
     *         immutablecollections.exceptions.ImIndexOutOfBoundsException: The collection is empty but indexStartingAtZero was 0
     *     onArray(1, 2).get(2)     =>
     *         immutablecollections.exceptions.ImIndexOutOfBoundsException: the size of the collection is 2 but indexStartingAtZero was 2
     *     
     * @throws IndexOutOfBoundsException
     */
    public T get(int indexStartingAtZero)
    {
        ImIndexOutOfBoundsException.check0(indexStartingAtZero, size(), "indexStartingAtZero");
        return get1(indexStartingAtZero + 1);
    }

    /**
     * Remove the element at index `indexStartingAtOne`.
     * 
     * All elements with `index >= indexStartingAtOne` are shuffled down.
     * 
     * ### Examples:
     * 
     *     on(1, 8, 2, 3, 5).remove(2)  =>  [1, 2, 3, 5]
     *     on(1, 2, 3).remove(0)        =>  java.lang.IndexOutOfBoundsException: indexStartingAtOne should be >= 1  but was 0
     *     
     * @throws IndexOutOfBoundsException
     * @see {@link #remove(int)}
     */
    public ImShelf<T> remove1(int indexStartingAtOne)
    {
        ImIndexOutOfBoundsException.check(indexStartingAtOne, size(), "indexStartingAtOne");
        ImTreeZipper<T> path = ImTreeZipper.onRoot(getTree()).goToIndex(indexStartingAtOne);

        return new ImShelf<T>(path.removeNode().close());
    }

    /**
     * Remove the element at index `indexStartingAtZero`.
     * 
     * All elements with `index >= indexStartingAtZero` are shuffled down.
     * 
     * ### Examples:
     * 
     *     on(1, 8, 2, 3, 5).remove(1)  =>  [1, 2, 3, 5]
     *     on(1, 2, 3).remove(-1)       =>  java.lang.IndexOutOfBoundsException: indexStartingAtZero should be >= 0  but was -1
     *     
     * @throws IndexOutOfBoundsException
     * @see {@link #remove1(int)}
     */
    public ImShelf<T> remove(int indexStartingAtZero)
    {
        ImIndexOutOfBoundsException.check0(indexStartingAtZero, size(), "indexStartingAtZero");
        return remove1(indexStartingAtZero + 1);
    }

    /**
     * `true` if `this` contains `elementToLookFor`, `false` otherwise.
     * 
     * More formally, returns `true` if and only if `this` contains
     * at least one element `e` such that
     * 
     *     e.equals(elementToLookFor)
     *
     * ### Examples:
     * 
     *     on(1, 2, 1).contains(1)     =>  true
     *     on(1, 2, 1).contains(null)  =>  throws java.lang.NullPointerException: ImCollections can't contain nulls
     */
    @Override
    public boolean contains(Object elementToLookFor)
    {
        return indexOf1(elementToLookFor) != -1;
    }

    /**
     * Returns the index (starting at one) of the first occurrence of `elementToLookFor`,
     * or -1 if no such element exists.
     * 
     * More formally, returns the lowest index `i` such that
     * 
     *     get1(i).equals(elementToLookFor)
     *     
     * or `-1` if there is no such index.
     * 
     *     on(1, 2, 3).indexOf(1)      =>  1
     *     on(1, 2, 3).indexOf(1.0)    =>  -1
     *     on(1, 2, 1).contains(null)  =>  throws java.lang.NullPointerException: ImCollections can't contain nulls
     *     
     * @see #indexOf0(Object)
     */
    public int indexOf1(Object elementToLookFor)
    {
        NullCheck.checkThrowingNPE(elementToLookFor);

        int index = 0;
        for (T thing : this)
        {
            index++;
            if (thing.equals(elementToLookFor))
                return index;
        }

        return -1;
    }

    /**
     * Returns the index (starting at zero) of the first occurrence of `elementToLookFor`,
     * or -1 if no such element exists.
     * 
     * More formally, returns the lowest index `i` such that
     * 
     *     get(i).equals(elementToLookFor)
     *     
     * or `-1` if there is no such index.
     * 
     *     on(1, 2, 3).indexOf(1)      =>  0
     *     on(1, 2, 3).indexOf(1.0)    =>  -1
     *     on(1, 2, 1).indexOf(null)   =>  throws java.lang.NullPointerException: ImCollections can't contain nulls
     *     
     * @see #indexOf1(Object)
     */
    public int indexOf(Object elementToLookFor)
    {
        return indexOf1(elementToLookFor) - 1;
    }

    ImShelfZipper<T> getZipperOnIndex(int indexStartingAtOne)
    {
        ImMaybe<ImTreeZipper<T>> m = ImTreeZipper.onIndex(getTree(), indexStartingAtOne);

        if (m.hasValue())
        {
            return new ImShelfZipper<T>(this, m.getValue());
        }
        else
        {
            throw new NoSuchElementException();
        }
    }

    /**
     * A zipper on `this`.
     * 
     * A *zipper* is a bit like a standard java iterator that lets you "mutate" the underlying collection.
     * 
     * Zippers allows you to navigate backwards and forwards in the shelf and to insert/replace/remove elements efficiently in batches.
     * The efficiency comes from the fact that the changes are made to the zipper rather than to the shelf directly
     * and several changes can be made in a batch. It is only when you close the zipper that you can see the changes.
     * 
     * Of course, shelfs are immutable so the underlying shelf does not change. In fact, zippers are also immutable
     * so as you "change" the zipper you are actually creating a new zipper.
     * Each time you close a zipper you will create a new shelf (provided you have made changes).
     * 
     * See the <a href="{@docRoot}/immutablecollections/package-summary.html">package summary</a>
     * for details of how zippers work.
     */
    public ImShelfZipper<T> getZipper()
    {
        return new ImShelfZipper<T>(this, ImTreeZipper.onLeftmost(getTree()).before());
    }

    /**
     * The shelf where the i-th element is the result of evaluating the single argument function `fn` on
     * the i-th element of `this`.
     * 
     * See the <a href="{@docRoot}/immutablecollections/functions/package-summary.html">package summary</a>
     * for more details about functions.
     * 
     * ### Examples:
     * 
     * To convert a list of objects to a list of their string representations:
     * 
     *     Function1<String> toStringFn = FnFactory.on(Object.class).getFn(String.class, "toString");
     *     onArray(1, 2).map(toStringFn) =>  "[1, 2]"
     * 
     * To parse a list of strings to their `Integer` equivalents:
     * 
     *     Function1<Integer> parseIntFn = FnFactory.on(Integer.class).getFnStatic(int.class, "parseInt", String.class);
     *     ImShelf.onArray("1", "2").map(parseIntFn)  =>  [1, 2]
     * 
     * To parse with a radix of `16`, we first get the parse function with two arguments, then we create a new function
     * out of this with the arguments reversed. Then, if we supply the radix argument of `16` to this function,
     * we will have a new function of one argument that does what we want:
     * 
     *     Function2<Integer> parseIntWithRadixFn = FnFactory.on(Integer.class).getFnStatic( //
     *             int.class, "parseInt", String.class, int.class);
     * 
     *     Function1<Integer> parseHexFn = parseIntWithRadixFn.flip().invoke(16);
     *     ImShelf.onArray("8", "D", "15").map(parseHexFn)  =>  [8, 13, 21]
     * 
     * @see immutablecollections.functions
     * @see #fold
     */
    public <O> ImShelf<O> map(Function1<O> fn)
    {
        ImShelf<O> mapped = ImShelf.empty();
        for (Object element : this)
        {
            mapped = mapped.adding(fn.invoke(element));
        }

        return mapped;

        // This was my first attempt - but it does not run fn on the elements in a predictable order.
        // Hmm - of course this would not matter in a pure functional language...
        // return new ImShelf<O>(getTree().map(fn));
    }

    ImTree<T> getTree()
    {
        return tree;
    }

    /**
     * The ImShelf formed out of the elements of each collection in `collections` in order.
     * 
     * ImCollections can't contain `null` so none of the elements can be `null`
     * 
     * ### Examples:
     * 
     *     List<Number> threeFive = Arrays.<Number> asList(3, 5);
     *     ImShelf<Integer> oneTwo = ImShelf.on(1, 2);
     * 
     *     concat(oneTwo, threeFive)          =>  [1, 2, 3, 5]");
     *     concat(oneTwo, threeFive, oneTwo)  =>  [1, 2, 3, 5, 1, 2]
     *     concat(on(), on())                 =>  []
     * 
     * @see #addingAll(Collection)
     * @see #joinIterator(Iterator)
     * @see #join(Collection)
     */
    public static <A> ImShelf<A> joinArray(Collection<? extends A>... collections)
    {
        return joinIterator(ArrayIterator.on(collections));
    }

    /**
     * The ImShelf formed out of the elements of each collection in `iterator` in order.
     * 
     * ImCollections can't contain `null` so none of the elements can be `null`
     * 
     * @see #addingAll(Collection)
     * @see #joinArray(Collection...)
     * @see #join(Collection)
     */
    public static <A> ImShelf<A> joinIterator(Iterator<Collection<? extends A>> iterator)
    {
        ImShelf<A> concat = ImShelf.empty();

        while (iterator.hasNext())
            concat = concat.addingAll(ImShelf.onAll(iterator.next()));

        return concat;
    }

    /**
     * The ImShelf formed out of the elements of each collection in `collectionOfCollections` in order.
     * 
     * ImCollections can't contain `null` so none of the elements can be `null`
     * 
     * @see #addingAll(Collection)
     * @see #joinArray(Collection...)
     * @see #joinIterator(Iterator)
     */
    public static <A> ImShelf<A> join(Collection<? extends Collection<? extends A>> collectionOfCollections)
    {
        return joinIterator((Iterator<Collection<? extends A>>) collectionOfCollections.iterator());
    }

    /**
     * The ImShelf formed out of the elements of `this` followed by the elements in `other` in order.
     * 
     * ImCollections can't contain `null` so none of the elements can be `null`
     * 
     * @see #join(Collection)
     * @see #joinArray(Collection...)
     * @see #joinIterator(Iterator)
     */
    public ImShelf<T> addingAll(Collection<? extends T> other)
    {
        ImShelf<T> otherShelf = ImShelf.onAll(other);
        return new ImShelf<T>(ImTree.merge(tree, otherShelf.getTree()));
    }

    /**
     * Compares `another` with `this` for equality.
     * 
     * Returns `true` if and only if the specified object is also an `ImShelf`, both
     * lists have the same size, and all corresponding pairs of elements in
     * the two lists are *equal*.
     * 
     *  `e1` and `e2` being *equal* means
     * 
     *     e1.equals(e2) == true
     * 
     * In other words, two ImShelfs are defined to be
     * *equal* if they contain *equal* elements in the same order.
     * 
     * In *other* other words - this is very similar to the standard Java List `equals`.
     *
     */
    @Override
    public boolean equals(Object other)
    {
        return this == other
                ? true
                : other instanceof ImShelf
                        ? eq((ImShelf<?>) other)
                        : false;
    }

    private boolean eq(ImShelf<?> otherShelf)
    {
        return size() == otherShelf.size() && hashCode() == otherShelf.hashCode()
                ? elementsEq(iterator(), otherShelf.iterator())
                : false;
    }

    private boolean elementsEq(ImShelfIterator<?> itOne, ImShelfIterator<?> itTwo)
    {
        while (itOne.hasNext())
        {
            if (!itOne.next().equals(itTwo.next()))
                return false;
        }
        return true;
    }

    /**
     * The hash code value for `this`.
     *
     * Because a shelf is immutable, the hash code is calculated only once when the shelf is
     * created and cached.
     * 
     * This implementation uses a different algorithm from that used in {@link ImList#hashCode()}.
     * 
     * The hash code for a shelf is the sum of the hash codes of its elements. In this regard it
     * is similar to the algorithm used by `java.util.AbstractSet`
     *
     */
    @Override
    public int hashCode()
    {
        return tree.hashCode();
    }
}
